//package work.rightAnswer;
//
//import java.util.ArrayList;
//import java.util.List;
//
//class Solution_39 {
//    List<List<Integer>> res;
//    List<Integer> path;
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        //求组合总和为target的组合 回溯
//        res = new ArrayList<>();
//        path = new ArrayList<>();
//
//        backtracing(candidates,target,0,0);
//        return res;
//    }
//
//
//    //获取总和为target的所有组合(可重复选取当前元素，但组合不能重复)，candidates:目标数组，target：值,sum:总和,startIndex:起始索引
//    //组合问题：要有一个起始索引变量startIndex，这个变量保证了每次递归只取（或当前）后面的元素，从而保证了顺序的唯一性，也就保证了组合的唯一性
//    public void backtracing(int[] candidates,int target,int sum,int startIndex){
//        //终止条件：当值>target时，return
//        if(sum>target){
//            return;
//        }
//        //判断等于时，加入res，return
//        if(sum==target){
//            res.add(new ArrayList<>(path));
//            return;
//        }
//
//
//        for (int i = startIndex; i < candidates.length; i++) {
//            sum+=candidates[i];
//            path.add(candidates[i]);
//            backtracing(candidates,target,sum,i);
//            path.remove(path.size()-1);
//            sum-=candidates[i];
//
//        }
//
//    }
//
//
//}